package com.xiangge.array;
/*
    查找算法：
       -- 线性查找：
            描述： 从前往后/从后往前一顺查找元素
            性能： 不稳定       不推荐
       -- 二分查找/折半查找：
            前提：
                1. 容器是数组： 长度一但确定不能改变
                2. 数组中元素有序：从小到大  /   从大到小

        随堂练习： 查找元素28在数组{5, 12, 90, 18, 77, 76, 45, 28, 59, 72}中的位置
 */
public class ArrayDemo3 {
    public static void main(String[] args) {
        // 1. 准备一个有序的数组
        int[] arr = {5, 12, 18, 28, 45, 59, 72, 76, 77, 90};
        // 2. 定义最小,最大,中间索引
        int minIndex = 0, maxIndex = arr.length-1 , mid;
        // 定义要查找的元素
        int num = 76;
        // 3. 使用死循环模拟二分查找过程
        while (minIndex <= maxIndex) {
            // 3.1 计算中间索引
            mid = (minIndex + maxIndex) / 2;
            // 3.2 比较arr[mid] 和 num 的大小
            if(num < arr[mid]){ // 处理num < arr[mid] 的情况
                maxIndex = mid - 1;
            }
            else if(num > arr[mid]){// 处理num > arr[mid] 的情况
                minIndex = mid + 1;
            }
            else{// 处理num == arr[mid] 的情况
                System.out.println(num+"在数组中的索引位置为：" + mid);
                return; // 找到就结束二分查找
            }
        }
        System.out.println(num+"在数组中不存在！");
    }
    public static void main2(String[] args) {
        // 1. 准备一个有序的数组
        int[] arr = {5, 12, 18, 28, 45, 59, 72, 76, 77, 90};
        // 2. 定义最小,最大,中间索引
        int minIndex = 0, maxIndex = arr.length-1 , mid;

        // 定义要查找的元素
        int num = 60;

        // 3. 使用死循环模拟二分查找过程
        while (true) {
            // 3.1 计算中间索引
            mid = (minIndex + maxIndex) / 2;

            // 3.2 比较arr[mid] 和 num 的大小
            if(num < arr[mid]){ // 处理num < arr[mid] 的情况
                maxIndex = mid - 1;
            }
            else if(num > arr[mid]){// 处理num > arr[mid] 的情况
                minIndex = mid + 1;
            }
            else{// 处理num == arr[mid] 的情况
                System.out.println(num+"在数组中的索引位置为：" + mid);
                break; // 找到就结束二分查找
            }

            // 没有找到，检查 minIndex 是都大于 maxIndex
            if(minIndex > maxIndex){
                System.out.println(num+"在数组中不存在！");
                break; // 不存在也结束二分查找
            }
        }
    }
    public static void main1(String[] args) {
        // 1. 准备一个数组：{3,5,4,2,1}
        int[] arr = {5, 12, 90, 18, 77, 76, 45, 28, 59, 72};

        int index = -1;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] == 59){
                index = i;
                break;
            }
        }

        // 判断index
        if(index == -1){
            System.out.println("59在数组中不存在！");
        }
        else{
            System.out.println("59在数组中的索引为：" + index);// 59在数组中的索引为：8
        }
    }
}
